package com.example.myletcodelearing.one

import java.lang.StringBuilder
import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashMap
import kotlin.math.abs


/**
 * @author tgw
 * @date 2022/11/7
 *给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

https://blog.csdn.net/u010365819/article/details/121000532
 */

fun main(args: Array<String>) {
    var op = Solution20.Solution()
    var num = arrayOf(10, 9, 2, 5, 3, 7, 101, 18)
    var result = op.lengthOfLIS(num)
    var result1 = op.lengthOfLIS2(num)

    print("打印：$result")
    print("打印：$result1")

}

private class Solution20 {
    internal class Solution {
        fun findNum(num: Array<Int>): Int {
            var newNum = ArrayList<ArrayList<Int>>()
            newNum.add(arrayListOf(num[0]))

            var map = ArrayList<Int>()

            for (i in 0 until num.size) {

                var size = f(i, num, map)
                map.add(size)

            }

            print("打印：$newNum")
            print("打印：${map}")
            return newNum.size
        }

        fun f(n: Int, num: Array<Int>, map: ArrayList<Int>): Int {
            var n = n
            if (n == 0) {
                return 1
            }
            var current = n
            while (num[current] < num[n - 1]) {
                n--
                return f(n - 1, num, map) + 1
            }
            return 1
        }

        fun lengthOfLIS(nums: Array<Int>): Int {
            if (nums.size == 0) {
                return 0
            }
            val dp = IntArray(nums.size)
            //初始化就是边界情况
            dp[0] = 1
            var maxans = 1
            //自底向上遍历
            for (i in 1 until nums.size) {
                dp[i] = 1
                //从下标0到i遍历
                for (j in 0 until i) {
                    //找到前面比nums[i]小的数nums[j],即有dp[i]= dp[j]+1
                    if (nums[j] < nums[i]) {
                        //因为会有多个小于nums[i]的数，也就是会存在多种组合了嘛，我们就取最大放到dp[i]
                        dp[i] = Math.max(dp[i], dp[j] + 1)
                    }
                }
                //求出dp[i]后，dp最大那个就是nums的最长递增子序列啦
                maxans = Math.max(maxans, dp[i])
            }
            return maxans
        }

        //[10,9,2,5,3,7,101,18]
        fun lengthOfLIS2(nums: Array<Int>): Int {
            if (nums.size == 0) {
                return 0
            }
            val dp = IntArray(nums.size)
            dp[0] = 1
            var maxans = 0
            for (i in 0 until nums.size){
                dp[i] = 1
                for (j in 0 until i+1){
                    if (nums[j]>nums[i]){
                        dp[i] = Math.max(dp[i]+1, dp[j])
                    }

                }
                //求出dp[i]后，dp最大那个就是nums的最长递增子序列啦
                maxans = Math.max(maxans, dp[i])
            }
            return maxans
        }
        //[10,9,2,5,3,7,101,18]
//        fun lengthOfLIS3(nums: Array<Int>): Int {
//            if (nums.size == 0) {
//                return 0
//            }
//            val dp = ArrayList<ArrayList<Int>>()
//            var arr0 = arrayListOf(nums[0])
//            dp.add(arr0)
//            var maxans = arr0
//            for (i in 0 until nums.size){
//                dp[i] = ArrayList()
//                dp[i].add(nums[i])
//                for (j in 0 until i+1){
//                    if (nums[j]<nums[i]){
//
//                        dp[i].add()
//                    }
//
//                }
//                //求出dp[i]后，dp最大那个就是nums的最长递增子序列啦
//                maxans = Math.max(maxans, dp[i])
//            }
//            return maxans
//        }

    }

}
